/*
{
    //坐标
    x
    y
    //步数
    s
    //优先级
    l
}
*/
let mapout 
//加载方法
function loadIng(arr,obs){
    let map = setObstacle(arr, obs, "x")
    mapout = map
    return map
}
//初始化,生成二维数组
function initialArray(x,y){
    let result = []
    for(let m = 0; m < x; m++){
        let arr = []
        for(let n = 0; n < y; n++) {
            arr.push(0)
        }
        result.push(arr)
    }
    return result
}
//生成障碍物
function setObstacle(mapArray, obsArray, obs){
    obsArray.forEach(e => {
        if(e[0] < mapArray.length && e[0] > -1) {
            if(e[1] < mapArray[e[0]].length && e[1] > -1) {
                mapArray[e[0]][e[1]] = obs
            }else {
                console.log(e)
            }
        } else {
            console.log(e)
        }
    });
    return mapArray
}
//地图可视化读取
function getHtmlObstacle() {
    let obj = {
        w:[]
    }
    let uls = es(".ul")
    let x = uls.length
    let y = uls[0].querySelectorAll(".li").length
    obj.range = [x,y]
    let li = es(".li")
    li.forEach(e => {
        if (e.classList.contains("b")) {
            obj.b = [Number(e.getAttribute("data-x")), Number(e.getAttribute("data-y"))]
            console.log('读取起点成功')
        }
        if (e.classList.contains("e")) {
            obj.e = [Number(e.getAttribute("data-x")), Number(e.getAttribute("data-y"))]
            console.log('读取终点成功')
        }
        if (e.classList.contains("w")) {
            obj.w.push([Number(e.getAttribute("data-x")), Number(e.getAttribute("data-y"))])
            console.log('读取障碍物成功')
        }
    })
    return obj
}
//v-m
function surface(){
    
}
//计算距离
function countDistance(a1, a2){
    return Math.abs(a1[0]-a2[0])+Math.abs(a1[1]-a2[1]);
}
//开始搜索
function run(x1,y1,x2,y2,arr,obs){
    //地图初始化 包含地图生成，障碍物生成
    let map = loadIng(arr,obs)
    //准备执行栈
    let stack = []
    //设置起点
    map[x1][y1] = 1
    //console.log(map)
    
    //寻找起点周围的路径
    let roadList = getAround(x1,y1,map.length,map[0].length)
    //筛选出未执行过的周围路径
    roadList = unSign(map,roadList,0)
    sign(map,roadList,map[x1][y1] + 1)
    roadList.forEach(e=>{
        let l = countDistance(e,[x2,y2])
        let s = map[e[0]][e[1]]
        let obj = {
            x:e[0],
            y:e[1],
            s:s,
            l: s + l
        }
        //排入优先级插入
        sortList(stack,obj)
    })
    if(map[x2][y2] === 0) {
        search(stack,map,x2,y2)
    } else {
        console.log("搜索完毕")
        return map
    }
    //console.log(map)
}
//筛选未执行
function unSign(map,arr,param) {
    let result = []
    arr.forEach((e)=>{
        if(map[e[0]][e[1]] === param) {
            result.push(e)
        }
    })
    //console.log(result)
    return result
}
//已执行标记
function sign(map,arr,param){
    arr.forEach((e)=>{
        if(map[e[0]][e[1]] === 0 && arr.length > 0) {
            map[e[0]][e[1]] = param
        }
    })
}
//搜索方法
function search(stack,map,x2,y2){
    if(stack.length === 0) {
        console.log("无法到达")
        console.log(map)
        return
    }
    let obj = stack[0]
    let roadList = getAround(obj.x, obj.y, map.length, map[0].length)
    roadList = unSign(map, roadList, 0)
    sign(map, roadList, obj.s + 1)
    stack.shift()
    roadList.forEach(e=>{
        let l = countDistance(e,[x2,y2])
        let s = map[e[0]][e[1]]
        let obj1 = {
            x:e[0],
            y:e[1],
            s:s,
            l: s + l
        }
        //排入优先级插入
        sortList(stack,obj1)
        
    })
    if(map[x2][y2] === 0 || stack.length === 0) {
        search(stack,map,x2,y2)
    } else {
    console.log("搜索完毕")
    console.log(map)
        return
    }
}
//获取周围格子
function getAround(x,y,xl,yl){
    let result = []
    //left
    if(x > -1 && x < xl && y - 1 > -1 && y < yl) {
        result.push([x, y - 1])
    }
    //right
    if(x > -1 && x < xl && y > -1 && y + 1 < yl) {
        result.push([x, y + 1])
    }
    //top
    if(x - 1 > -1 && x < xl && y > -1 && y  < yl) {
        result.push([x - 1, y])
    }
    //bottom
    if(x > -1 && x + 1 < xl && y > -1 && y  < yl) {
        result.push([x + 1, y])
    }
    return result
}
//优先级排序
function sortList(arr,obj){
    if(arr.length === 0) {
        arr.push(obj)
    } else {
    for(let i = 0; i < arr.length; i++) {
        let item = arr[i]
        if(!(obj.l > item.l)) {
            arr.splice(i,0,obj)
            return
        }
    }
    arr.push(obj)
    }
}

function s(element) {
    return document.querySelector(element)
}
function es(element) {
    return document.querySelectorAll(element)
}
function setRoad(end, range, map) {
    if (map[end[0]][end[1]] !== 2) {
        let result = getAround(end[0], end[1], range[0], range[1])
        for (let i = 0; i < result.length; i++) {
            let e = result[i]
            if (map[e[0]][e[1]] === map[end[0]][end[1]] - 1) { 
                let ul = es(".ul")
                let li = ul[e[0]].querySelectorAll(".li")
                li[e[1]].classList.add("r")
                setRoad(e, range, map)
                break
            }
        }
    } else {
       
    }
}
(function (){
    let play = s(".play")
    play.addEventListener("click", () => {
        alert("开始搜索")
        let obj = getHtmlObstacle()
        run(obj.b[0], obj.b[1], obj.e[0], obj.e[1], initialArray(obj.range[0], obj.range[1]), obj.w)
        setRoad(obj.e, obj.range, mapout)
    })
})()
